package Z.dailyExercise._0111;

public class _剑指Offer11_旋转数组的最小数字 {
    public static void main(String[] args) {
        _剑指Offer11_旋转数组的最小数字 te = new _剑指Offer11_旋转数组的最小数字();
        System.out.println(te.minArray(new  int[]{3,1}));

    }
    /**
     * 自解：找最小的数字 其实就是找最大数值右边的第一个
     * 最大数值：比最后一位数字大的从右边起的第一位
     * ==暴力寻找,可能有313这样 同时为了避免122--一直吃错
      * @param numbers
     * @return
     */
    public int minArray(int[] numbers) {
        boolean roate = false;
        int last = numbers[numbers.length-1];
        for (int i= numbers.length-1;i>=0;i--){
            if (numbers[i]> last || (numbers[i]== last && i<numbers.length-2)){
                last =i;
                roate = true;
                break;
            }
        }

        if (roate){
            return numbers[last+1];
        }else {
            return numbers[0];
        }


    }

    /**
     * 二分查找--找最小的那个点
     * --有三种情况
     * mid数值更小 结果在左侧 由于可能mid'就是最小值 所以 high = pivot
     * mid数值更大 结果在右侧 因为mid已经不可能是最小值了 所以low = pivot+1
     * 如果相等 可能左右是凹型地段 所以就强制缩小范围 high--
     *
     */
    public int minArray1(int[] numbers) {
        int low =0;
        int high = numbers.length-1;

        while (low<high){
            int pivot = low+(high-low)/2;

            if (numbers[pivot]<numbers[high]){
                high = pivot;
            }else if (numbers[pivot]>numbers[high]){
                low = pivot+1;
            }else {
                high -= 1;
            }
        }

        return numbers[low];
    }
}
